package com.peng.leetcode.string;

import java.util.HashMap;
import java.util.Map;
import java.util.PriorityQueue;

/**
 * ReorganizeString
 * 767. 重构字符串
 * https://leetcode.cn/problems/reorganize-string/
 *
 * @author: lupeng6
 * @create: 2023/2/22 20:16
 */
public class ReorganizeString {

    public static void main(String[] args) {
        System.out.println(new ReorganizeString().reorganizeString("vvvlo"));
    }

    public String reorganizeString(String s) {
        int maxCount = 0;
        Map<Character, Integer> countMap = new HashMap<>();
        for (int i = 0; i < s.length(); i++) {
            char c = s.charAt(i);
            countMap.compute(c, (key, val) -> {
                if (val == null) {
                    return 1;
                } else {
                    return val + 1;
                }
            });
            maxCount = Math.max(maxCount, countMap.get(c));
        }
        if (maxCount > (s.length() + 1) / 2) {
            return "";
        }

        StringBuilder res = new StringBuilder();

        PriorityQueue<Node> q = new PriorityQueue<>((a, b) -> b.count - a.count);
        countMap.forEach((key, count) -> {
            q.offer(new Node(key, count));
        });
        while (q.size() >= 2) {
            Node n1 = q.poll();
            Node n2 = q.poll();
            res.append(n1.key);
            res.append(n2.key);
            countMap.put(n1.key, countMap.get(n1.key) - 1);
            countMap.put(n2.key, countMap.get(n2.key) - 1);
            if (countMap.get(n1.key) > 0) {
                q.offer(new Node(n1.key, countMap.get(n1.key)));
            }
            if (countMap.get(n2.key) > 0) {
                q.offer(new Node(n2.key, countMap.get(n2.key)));
            }
        }
        if (q.size() > 0) {
            res.append(q.poll().key);
        }
        return res.toString();
    }

    static class Node {
        char key;
        int count;

        public Node() {
        }

        public Node(char key, int count) {
            this.key = key;
            this.count = count;
        }
    }
}
